package jm.algorithm.back_tracking;

/**
 * @Description 成员变量优化 n 皇后
 * @date 2022/5/19 19:38
 */
public class QueensVar {
    public static void main(String[] args) {
        new QueensVar().placeQueens(4);
    }

    // 判断当前列中是否已经存在皇后
    // cols[0] = true 即 0 列已经存在皇后
    boolean[] cols;

    // 判断 左上角 到 右下角 是否有皇后 即 ↘ 方向
    boolean[] leftTop;

    // 判断 右上角 到 左下角 是否有皇后 即 ↙ 方向
    boolean[] rightTop;

    // 统计摆法
    int ways;

    /**
     * n 皇后问题
     * @param n
     */
    void placeQueens(int n){
        if (n < 1) return;
        // 初始化数组值
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[(n << 1) - 1];
        place(0);
        System.out.println(ways);
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row 行
     */
    void place(int row){
        // 如果上一行摆放成功了，即符合所有摆放条件，最后一行不需要调用。
        if (row == cols.length) {
            ways++;
            return;
        }

        for (int col = 0; col < cols.length; col++) {
            // 不能摆就返回
            if (cols[col]) continue;
            int lIndex = row - col + cols.length - 1;
            int rIndex = row + col;
            if (leftTop[lIndex]) continue;
            if (rightTop[rIndex]) continue;

            // 摆放皇后
            cols[col] = true;
            leftTop[lIndex] = true;
            rightTop[rIndex] = true;
            // 在下一行摆放皇后
            place(row + 1);
            // 回溯
            // 如果将某行的所有可能都摆放完了，会返回到他的上行中，对这行重新摆放，就实现了回溯;


            // 对于布尔类型，回溯时需要重置
            // 如果不重置，回溯之后的值也会是true，即已经存在皇后的情况，永远无法摆放。
            cols[col] = false;
            leftTop[lIndex] = false;
            rightTop[rIndex] = false;
        }
    }
}
